#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <math.h>

using namespace std;

// 2156. 查找给定哈希值的子串
// https://leetcode.cn/problems/find-substring-with-given-hash-value/description/

class Solution1
{
public:
    long long power(long long base, int exp, int mod)
    {
        long long result = 1;
        while (exp > 0)
        {
            if (exp % 2 == 1)
                result = result * base % mod;
            base = base * base % mod;
            exp /= 2;
        }
        return result;
    }
    int hash(string s, int p, int m)
    {
        long long ret = 0;
        for (int i = 0; i < s.size(); i++)
        {
            ret = (ret + (s[i] - 'a' + 1) * power(p, i, m)) % m;
        }
        return ret;
    }
    string subStrHash(string s, int power, int modulo, int k, int hashValue)
    {
        int right = 0;
        for (int i = 0; i < s.size(); i++)
        {
            string curStr(s.begin() + right, s.begin() + i + 1);
            int curHash = hash(curStr, power, modulo);

            if (i - right + 1 < k)
            {
                continue;
            }

            if (curHash == hashValue)
            {
                return curStr;
            }
            if (i - right > 1)
            {
                i--;
            }
            right++;
        }
        return "str";
    }
};

class Solution
{
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue)
    {

        long long initHash = 0;
        long long p = 1;

        int n = s.size();

        for (int i = n - k; i < n; i++)
        {
            initHash = (initHash + (s[i] - 'a' + 1) * p % modulo) % modulo;
            if (i != (n - 1))
            {
                p = p * power % modulo;
            }
        }
        int ans = n - 1;
        int right = n - 1;
        if (initHash == hashValue)
        {
            ans = n - k;
        }
        for (int i = n - k - 1; i >= 0; i--)
        {
            initHash = (initHash - ((s[right] - 'a' + 1) * p % modulo) + modulo) % modulo;
            initHash = (initHash * power) % modulo;
            initHash = ((s[i] - 'a' + 1) + initHash) % modulo;

            if (initHash == hashValue)
            {
                ans = i;
            }
            right--;
        }
        return s.substr(ans, k);
    }
};

int main()
{
    return 0;
}